import java.util.*;
 public class TreeNode {
     int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
       this.val = val;
    }
 }

public class Solution {
    int ret = -1010;
    public int maxPathSum (TreeNode root) {
        dfs(root);
        return ret;
    }
    int dfs(TreeNode root) {
        if(root == null) return 0;
        int l = Math.max(0, dfs(root.left)); // 左⼦树为根的最⼤单链和
        int r = Math.max(0, dfs(root.right)); // 右⼦树为根的最⼤单链和 // 经过root的最⼤路径和
        ret = Math.max(ret, root.val + l + r);
        return root.val + Math.max(l, r);
    }
}
